package com.my.lock.v21;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.atomic.AtomicReference;

/**
 * Created by ZhongGang
 * at 2018/7/30 11:19
 * <p>
 * 先入先出线程安全队列实现
 */
public class Queue<E> {
    private static final Logger LOGGER = LoggerFactory.getLogger(Queue.class);

    private AtomicReference<Node<E>> head = new AtomicReference<>(null);//头结点
    private AtomicReference<Node<E>> tail = new AtomicReference<>(null);//尾结点

    //入队操作
    public void enqueue(E e) {
        Node<E> newNode = new Node<>(e);
        if (!this.head.compareAndSet(null, newNode)) {
            while (true) {
                Node<E> tailNode = this.tail.get();
                if (this.tail.compareAndSet(tailNode, newNode)) {
                    if (tailNode == null) {
                        Node<E> headNode = this.head.get();
                        newNode.prev = headNode;
                        headNode.next = newNode;
                    } else {
                        tailNode.next = newNode;
                        newNode.prev = tailNode;
                    }
                    break;
                }
            }
        }
    }

    //出队操作
    public E dequeue() {
        while (true) {
            Node<E> headNode = this.head.get();
            if (headNode == null) {
                return null;
            }

            if (this.head.compareAndSet(headNode, headNode.next)) {
                Node<E> newHeadNode = this.head.get();
                if (newHeadNode != null) {
                    newHeadNode.prev = null;
                }
                return headNode.e;
            }
        }
    }

    @Override
    public String toString() {
        String result = "";
        Node<E> node = this.head.get();
        while (node != null) {
            result += node.e + " => ";
            node = node.next;
        }
        return result;
    }

    private static class Node<E> {
        private Node<E> prev;//前继节点
        private Node<E> next;//后继节点
        private E e;//节点持有数据

        Node(E e) {
            this.e = e;
        }
    }

    public static void main(String[] args) throws Exception {
        Queue<Integer> queue = new Queue<>();
        List<Thread> threads = new ArrayList<>();
        for (int i = 0; i < 20; i++) {
            int finalI = i;
            Thread thread = new Thread(new Runnable() {
                @Override
                public void run() {
                    queue.enqueue(finalI);
                }
            });
            threads.add(thread);
            thread.start();
        }

        for (Thread thread : threads) {
            thread.join();
        }

        LOGGER.info("queue: {}", queue);

        for (int i = 0; i < 20; i++) {
            Thread thread = new Thread(new Runnable() {
                @Override
                public void run() {
                    Integer dequeue = queue.dequeue();
                    LOGGER.info("dequeue: {}, queue: {}", dequeue, queue);
                }
            });
            threads.add(thread);
            thread.start();
        }

        for (Thread thread : threads) {
            thread.join();
        }

        LOGGER.info("queue: {}", queue);
    }

}
